﻿#include "knapsack.h"

/* Structs */
typedef struct {
	int value;
	int weight;
} itemT;

struct knapsackCDT {
	int nItems;
	int volume;
	itemT *items;
};

int counter = 0; //CriticalOp

/* Prototypes */
static knapsackADT newKnapsack(int size);
static knapsackADT loadKsFile(string fileName);
static void printKnapsack(knapsackADT ks);
static void initKnapMatrix(matrixADT matrix);
static int calculateKnapsack(knapsackADT ks, matrixADT matrix);
static int getMax(int a, int b);
void printOptimalItems(matrixADT matrix);

void runKnapsack() {
	int value;
	knapsackADT ks;
	matrixADT matrix;

	system("cls");
	printf("-- Knapsack problem --\n");
	printf("Recommended knapsacks: knapsackX.txt (X = 1-6)\n");
	printf("\n => ");
	ks = loadKsFile(Concat("./knapsack/", GetLine()));
	printf("\n");

	if (ks != NULL) {
		// nItems+1 eftersom vi även vill ha för 0 items
		matrix = NewGraph(ks->nItems+1, ks->volume+1);
		initKnapMatrix(matrix);
		//printKnapsack(ks);
		printf("Optimal value: %d\n", calculateKnapsack(ks, matrix));
		printOptimalItems(matrix, ks);
	}
	printf("\n");
	system("pause");
}

static knapsackADT newKnapsack(int size) {
	knapsackADT ks;

	ks = New(knapsackADT);
	ks->nItems = size;
	ks->items = NewArray(size, itemT);

	return ks;
}

static knapsackADT loadKsFile(string fileName) {
	FILE *infile;
	knapsackADT ks;
	int nItem, i;
	itemT item;

	if ((infile = fopen(fileName, "r")) != NULL) {
		fscanf(infile, "%d", &nItem);
		ks = newKnapsack(nItem);
		for (i=1; i<=nItem; i++) {
			fscanf(infile, "%*d %d %d", &item.value, &item.weight);
			ks->items[i] = item;
		}
		fscanf(infile, "%d", &ks->volume);
		fclose(infile);
	} else {
		printf("Couldn't open the selected knapsack.\n");
		ks = NULL;
	}

	return ks;
}

static void initKnapMatrix(matrixADT matrix) {
	int i;

	for (i=0; i<matrix->size; i++)
		matrix->nodes[i][0] = 0;

	for (i=0; i<matrix->size_y; i++)
		matrix->nodes[0][i] = 0;
}

static int calculateKnapsack(knapsackADT ks, matrixADT matrix) {
	int i, w, weight;

	for (i=1; i < matrix->size; i++) {
		for (w=1; w < matrix->size_y; w++) {
			if (ks->items[i].weight > w){//ks->volume) {
				matrix->nodes[i][w] = matrix->nodes[i-1][w];
				counter++; //CriticalOp
			} else {
				weight = w - ks->items[i].weight;
				if(weight < 0)
					weight = 0;
				matrix->nodes[i][w] = getMax(matrix->nodes[i-1][w], ks->items[i].value + matrix->nodes[i-1][weight]);
				counter++; //CriticalOp
			}
		}
	}
	i = matrix->size;
	w = matrix->size_y;
	return matrix->nodes[i-1][w-1];
}

static int getMax(int a, int b) {
	return (a > b ? a : b);
}

static void printKnapsack(knapsackADT ks) {
	int i;
	
	printf("Number of CriticalOp: %d\n", counter);
	printf("Number of items: %d\nVolume: %d\n", ks->nItems, ks->volume);
	for (i=1; i<=ks->nItems; i++)
		printf("Id: %d\tValue: %d\tWeight: %d\n", i, ks->items[i].value, ks->items[i].weight);
}
void printOptimalItems(matrixADT matrix, knapsackADT ks){
	int i, w=ks->volume;//ks->volume-1;

	printf("Items in solution (ID):");
	for (i=ks->nItems; i > 0; i--)
		if (matrix->nodes[i][w] != matrix->nodes[i-1][w]) {
			printf(" %d", i);
			w -= ks->items[i].weight;
		}
	printf("\n");
}